package array;

import java.util.HashMap;

public class BSinShiftArray {

    //search in a desc array left shift
	public static int bs(int[] array, int k) {
		int l = 0;
		int u = array.length - 1;
		while (u >= l) {
			int m = l + ((u - l) >> 1);
			if (array[m] == k)
				return m;
			if (array[l] < array[m]) {
				if (k >= array[l] && k < array[m])
					u = m - 1;
				else
					l = m + 1;
			} else if (array[l] > array[m]) {
				if (array[m] < k && k < array[u])
					l = m - 1;
				else
					u = m + 1;
			}
		}
		return -1;
	}
	
  public static int search(int a[], int l, int u, int x) {
    while (l <= u) {
      int m = (l + u) / 2;
      if (x == a[m]) {
        return m;
      } else if (a[l] <= a[m]) {
        if (x > a[m]) {
          l = m + 1;
        } else if (x >= a[l]) {
          u = m - 1;
        } else {
          l = m + 1;
        }
      } else if (x < a[m])
        u = m - 1;
      else if (x <= a[u])
        l = m + 1;
      else
        u = m - 1;
    }
    return -1;
  }
	
	//find max in a shifted sorted array
	public static int max(int array[]){
		int l = 0;
		int u = array.length - 1;
		int m = 0;
		while(u >= l){
			m = l + (u - l) / 2;
			if(m == array.length - 1 || m == 0)
				return m;
			if((array[m] > array[m+1] && array[m] > array[m-1]) && m < array.length - 1 && m > 0)
				return m;
			if(array[m] > array[l])
				l = m+1; 
			if(array[m] < array[u])
				u = m-1;
		}
		return m;
	}
	
	public static void missingNumber(int[] array){
	    if (array == null)
	    return;
	    int min = array[0];
	    int max = array[0];
	    for(int i = 1; i < array.length; i++){
	        if(array[i] > max)
	            max = array[i];
	        if(array[i] < min)
	            min = array[i];
	    }
	    
	    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	    for(int i = min; i <= max; i++)
	        map.put(i,1);
	        
	    for(int i = 0; i < array.length; i++)
	    if(map.containsKey(array[i]))
	    map.put(array[i],0);
	    
	    for(int key : map.keySet()){
	    if(map.get(key) == 1)
	        System.out.print(key + " ");
	    }
	    System.out.print("\n");
	    return;
	}
	
	public static int search(int[] A, int target) {
    // Start typing your Java solution below
    // DO NOT write main() function
   int l = 0 ; 
   int u = A.length-1;
   while(l <= u){
       int m = l + (u-l)/2;
       if(A[m] == target)
         return m;
    if(A[l] < A[m]){
        if(target >= A[l] && target < A[m])
          u = m -1;
        else
          l = m+1;
    } else if(A[l] > A[m]){
        if(A[m] < target && target < A[u])
          l = m+1;
        else
          u = m-1;
    }
       
   }
   return -1;
}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] data = new int[] {1};
		System.out.println(search(data, 0));
	}

}
